package code101_200.code10_20;

import java.util.ArrayList;
import java.util.List;

/**
 * 杨辉三角
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 *
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 *
 */
public class _118yangHuiSanJiao {

    /**
     * 初始一二行数据都为1，从第三行开始计算
     * 思考：好像只能暴力求解，一行一行进行数据便利，因为他要返回整个数组
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 36.1 MB     * , 在所有 Java 提交中击败了     * 75.32%     * 的用户
     *
     * @param numRows
     * @return
     */
    public static List<List<Integer>> generate(int numRows) {
        List<Integer> arr = new ArrayList<>();
        List<List<Integer>> row = new ArrayList<>();
        arr.add(1);
        row.add(arr);
        if(numRows==1) return row;
        List<Integer> arr2 = new ArrayList<>();
        arr2.add(1);
        arr2.add(1);
        row.add(arr2);
        if(numRows==2) return row;
        //第一层循环表示行
        for (int i = 3; i <= numRows; i++) {
            //第二层循环表示行中具体的数
            List<Integer> temp = new ArrayList<>();
            temp.add(1);
            for (int j = 0; j < i-2; j++) {
                arr = row.get(i-2);
                temp.add(arr.get(j)+arr.get(j+1));
            }
            temp.add(1);
            row.add(temp);
        }
        return row;
    }

    public static void main(String[] args) {
        for (List<Integer> arr : generate(4)) {
            for (Integer i : arr) {
                System.out.print(i+"  ");
            }
            System.out.println();
        }
    }

}
